﻿#include<iostream>

void MergeSort(int* arr, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}
	MergeSort(arr, begin, (begin+end) / 2);
	MergeSort(arr, (end + begin) / 2 + 1, end);

	int* temp = (int*)malloc(sizeof(int) * (end - begin + 1));
	int count = 0;
	int a = begin;
	int aend = (end + begin) / 2;
	int b = (end + begin) / 2 + 1;
	int bend = end;
	while (a <= aend && b <= bend)
	{
		if (arr[a] > arr[b])
		{
			temp[count++] = arr[b++];
		}
		else
		{
			temp[count++] = arr[a++];
		}
	}

	while (a <= aend)
	{
		temp[count++] = arr[a++];
	}
	while (b <= bend)
	{
		temp[count++] = arr[b++];
	}

	for (int i = 0; i < count; i++)
	{
		arr[begin++] = temp[i];
	}
	free(temp);
}

int main()
{
	int arr1[5] = { 1,2,3,4,5 };
	int arr2[6] = { 5,4,3,2,1,0 };
	int arr3[5] = { 1,1,2,1,1 };

	//归并排序
	MergeSort(arr1, 0, 4);
	MergeSort(arr2, 0, 5);
	MergeSort(arr3, 0, 4);

	for (int i = 0; i < 5; i++)
	{
		printf("%d ", arr1[i]);
	}
	printf("\n");
	for (int i = 0; i < 6; i++)
	{
		printf("%d ", arr2[i]);
	}
	printf("\n");
	for (int i = 0; i < 5; i++)
	{
		printf("%d ", arr3[i]);
	}
	printf("\n");
	return 0;
}